package main

//#link:https://leetcode-cn.com/problems/permutation-in-string/
import "fmt"

func main() {
	s1 := "ab"
	//s2 := "eidbaooo"
	s2 := "eidboaoo"
	fmt.Println(checkInclusion(s1, s2))
}

/**
 * @Description:给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 * @t:滑动窗口的思想
 */
func checkInclusion(s1 string, s2 string) bool {
	need, window := make(map[byte]int), make(map[byte]int)
	for _, letter := range []byte(s1) {
		need[letter]++
	}
	validLen := 0
	left, right := 0, 0
	for right < len(s2) {
		rLetter := s2[right]
		right++
		//判断字符是否要加入到窗口
		if value, ok := need[rLetter]; ok {
			window[rLetter]++
			if window[rLetter] == value {
				validLen++
			}
		}
		//判断窗口是否要缩小
		for right-left >= len(s1) {
			if validLen == len(need) {
				return true
			}
			lLetter := s2[left]
			left++
			if value, ok := need[lLetter]; ok {
				if window[lLetter] == value {
					validLen--
				}
				window[lLetter]--
			}
		}
	}
	return false
}
